package cn.hy.机考.part04;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author hy
 * <p>
 * 三十五、小朋友高矮排列
 * 以“高”“矮”“高”“矮”顺序排列，每一个“高”位置的小朋友要比相邻的位 置高或者相等;
 * 每一个“矮”位置的小朋友要比相邻的位置矮或者相等; 要求小朋友们移动的距离和最小，第一个从“高”位开始排，输出最小移动距离 即可。
 * 4 1 3 5 2
 * 输出:4 1 5 2 3
 * <p>
 * https://www.pudn.com/news/62b9b060f3cc394cf1d45696.html
 *
 *  https://blog.csdn.net/cxh21627/article/details/125209868
 * #解题想法：
 * 错误想法：一开始想法，list前后添加一个0，从位置1依次往后循环，由于list前面增加了个0，
 *
 * 所以i%2==1的位置是高值位，如果它不是包括它在内的前后三个元素最大值，那么就将它和i+1位置对换
 * （此处原因是身高>0,所以从位置1开始，如果存在比它大的值，肯定在他后面位置，
 * 因为前面一个数已经通过最小值判断了），
 * i%2==0的位置是低值位，如果它不是包括它在内的前后三个元素最小值，那么就将它和i+1位置对换。
 * 但这个想法不符合最小移动步数，测试用例10 8 6 9 9，最佳结果是一步--10 8 9 6 9，
 * 而不是两步--10 6 9 8 9
 *
 * 正确想法：通过整体观察，list前e个最大值最终结果肯定都在高值位，那么就通过深度复制生成新的
 * list排序，依次找高位置的数字在不在新的list，不在的话，肯定就在低位置，那么调换他们就可以了
 */
public class Demo35 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strs = sc.nextLine().split("\\s+");
        int[] arr = new int[strs.length];
        for (int i = 0; i < strs.length; i++) {
            arr[i] = Integer.parseInt(strs[i]);
        }
        int len = arr.length;
        for (int i = 0; i < len; ++i) {
            if (i % 2 == 0 && i < len - 1 && arr[i] < arr[i + 1]) swap(arr, i, i + 1);
            if (i % 2 == 1 && i < len - 1 && arr[i] > arr[i + 1]) swap(arr, i, i + 1);
        }

        System.out.println(Arrays.toString(arr));
    }


    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
